训练指南 UVALive - 5135 （双连通分量）

Diposting di | Edited on

Mining Your Own Business

UVALive - 5135

题意

在一张无向图中，将一些点涂上黑色，使得删掉图中任何一个点时，每个连通分量至少有一个黑点。问最少能涂几个黑点，并且在涂最少的情况下有几种方案。

显然，一定不能涂割点。对于每一个连通分量，如果有1个割点，则必须涂上分量内除割点之外的任意一个点，如果有多个（2个及以上）割点，则这个分量不需要涂色。如果整张图都没有割点，那么任选两个点涂色即可，之所以要涂两个，是要防止删掉的电恰是黑点的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

struct Edge{
    int u,v;
};
///割顶 bccno 无意义
int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cut;
vector<int>G[maxn],bcc[maxn];
stack<Edge>S;
int dfs(int u,int fa){
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for(int i = 0; i < G[u].size(); i++){
        int v =G[u][i];
        Edge e = (Edge){u,v};
        if(!pre[v]){ ///没有访问过
            S.push(e);
            child++;
            int lowv = dfs(v, u);
            lowu=min(lowu, lowv);                ///用后代更新
            if(lowv >= pre[u]){
                iscut[u]=true;
                bcc_cut++;bcc[bcc_cut].clear();   ///注意 bcc从1开始
                for(;;){
                    Edge x=S.top();S.pop();
                    if(bccno[x.u] != bcc_cut){bcc[bcc_cut].push_back(x.u);bccno[x.u]=bcc_cut;}
                    if(bccno[x.v] != bcc_cut){bcc[bcc_cut].push_back(x.v);bccno[x.v]=bcc_cut;}
                    if(x.u==u&&x.v==v)break;
                }
            }
        }
        else if(pre[v] < pre[u] && v !=fa){
            S.push(e);
            lowu = min(lowu,pre[v]);
        }
    }
    if(fa < 0 && child == 1) iscut[u] = 0;
    return lowu;
}
void find_bcc(int n){
    memset(pre, 0, sizeof(pre));
    memset(iscut, 0, sizeof(iscut));
    memset(bccno, 0, sizeof(bccno));
    dfs_clock = bcc_cut = 0;
    for(int i = 0; i < n;i++)
        if(!pre[i])dfs(i,-1);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,Case=1;
    int mx;
    while(cin>>n&&n){
        for(int i=0;i<2*n;i++)G[i].clear();
        mx=-inf;
        for(int i=0;i<n;i++){
            int u,v;
            cin>>u>>v;mx=max(mx,max(u,v));
            u--,v--;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        find_bcc(mx);
        ll ans1=0,ans2=1;
        for(int i=1;i<=bcc_cut;i++){
            int cut_cnt=0;
            for(int j=0;j<bcc[i].size();j++)
                if(iscut[bcc[i][j]])cut_cnt++;
            if(cut_cnt==1){
                ans1++;
                ans2*=(ll)(bcc[i].size()-cut_cnt);
            }
        }
        if(bcc_cut==1){
            ans1=2;
            ans2=ll(bcc[1].size()*(bcc[1].size()*1LL-1LL)/2LL);
        }
        cout<<"Case "<<Case++<<": "<<ans1<<" "<<ans2<<endl;
    }
    return 0;
}